// 版权所有2011 Go作者。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package strings

import (
	"io"
	"sync"
)

// Replacer用替换项替换字符串列表。
// 多个goroutine并发使用是安全的。
type Replacer struct {
	once   sync.Once // guards buildOnce方法
	r      replacer
	oldnew []string
}

// replacer是替换算法需要实现的接口。
type replacer interface {
	Replace(s string) string
	WriteString(w io.Writer, s string) (n int, err error)
}

// NewReplacer从旧的、新的字符串列表中返回一个新的替换项
// 对。替换按照它们在
// 目标字符串中出现的顺序执行，没有重叠匹配。旧字符串
// 按参数顺序进行比较。
// 
// 如果给定奇数个参数，则NewReplacer会出现恐慌。
func NewReplacer(oldnew ...string) *Replacer {
	if len(oldnew)%2 == 1 {
		panic("strings.NewReplacer: odd argument count")
	}
	return &Replacer{oldnew: append([]string(nil), oldnew...)}
}

func (r *Replacer) buildOnce() {
	r.r = r.build()
	r.oldnew = nil
}

func (b *Replacer) build() replacer {
	oldnew := b.oldnew
	if len(oldnew) == 2 && len(oldnew[0]) > 1 {
		return makeSingleStringReplacer(oldnew[0], oldnew[1])
	}

	allNewBytes := true
	for i := 0; i < len(oldnew); i += 2 {
		if len(oldnew[i]) != 1 {
			return makeGenericReplacer(oldnew)
		}
		if len(oldnew[i+1]) != 1 {
			allNewBytes = false
		}
	}

	if allNewBytes {
		r := byteReplacer{}
		for i := range r {
			r[i] = byte(i)
		}
		// 旧->新映射的第一次出现优先于具有相同旧字符串的其他映射。
		for i := len(oldnew) - 2; i >= 0; i -= 2 {
			o := oldnew[i][0]
			n := oldnew[i+1][0]
			r[o] = n
		}
		return &r
	}

	r := byteStringReplacer{toReplace: make([]string, 0, len(oldnew)/2)}
	// 第一次出现的旧->新映射优先于其他具有相同旧字符串的映射。
	for i := len(oldnew) - 2; i >= 0; i -= 2 {
		o := oldnew[i][0]
		n := oldnew[i+1]
		// 避免多次重复计数。
		if r.replacements[o] == nil {
			// 我们需要使用字符串（[]字节{o}）而不是字符串（o），
			// 以避免对o进行utf8编码。
			// 例如。字节（150）产生长度为2的字符串。
			r.toReplace = append(r.toReplace, string([]byte{o}))
		}
		r.replacements[o] = []byte(n)

	}
	return &r
}

// Replace返回一份执行了所有替换的s的副本。
func (r *Replacer) Replace(s string) string {
	r.once.Do(r.buildOnce)
	return r.r.Replace(s)
}

// WriteString在执行所有替换的情况下将s写入w。
func (r *Replacer) WriteString(w io.Writer, s string) (n int, err error) {
	r.once.Do(r.buildOnce)
	return r.r.WriteString(w, s)
}

// 三节点是查找trie中优先键/值对的节点。键
// 和值可能为空。例如，包含键“ax”、“ay”、
// /“bcbc”、“x”和“xy”的trie可以有八个节点：
// 
// n0-
// n1 a-
// n2.x+
// n3.y+
// n2和n3；n4的孩子是n5；n6的孩子是n7。节点n0、n1和n4（标记为
// 并带有尾随“-”）是部分键，节点n2、n3、n5、n6和n7 
// （标记为尾随“+”）是完整键。
type trieNode struct {
	// value是trie节点的键/值对的值。如果
	// 此节点不是完整密钥，则为空。
	value string
	// 优先级是trie节点的
	// 键/值对的优先级（越高越重要）；密钥不一定匹配最短或最长的
	// 第一个。如果此节点是完整密钥，则优先级为正，否则为零
	// 否则。在上面的示例中，正/零优先级标记为
	// 并带有尾随的“+”或“-”。
	priority int

	// trie节点可能有零个或多个子节点：
	// *如果剩余字段为零，则没有子节点。
	// /*如果prefix和next不为零，则next中有一个子项。
	// /*如果表为非零，则定义所有子项。
	// 
	// 当有一个子节点时，前缀优先于表，但为了提高查找效率，
	// 根节点始终使用表。

	// prefix是这个trie节点和下一个trie节点之间密钥的差异。
	// 在上面的示例中，节点n4具有前缀“cbc”，并且n4的下一个节点是n5。
	// 节点n5没有子节点，因此没有前缀、next和table字段。
	prefix string
	next   *trieNode

	// table是一个按键中的下一个字节索引的查找表，位于
	// 之后，通过GenericReplace.mapping重新映射该字节以创建密集的
	// 索引。在上面的示例中，键仅使用“a”、“b”、“c”、“x”和
	// /“y”，它们重新映射到0、1、2、3和4。所有其他字节重新映射为5，
	// GenericReplace.tableSize将为5。节点n0的表将是
	// /[]*三节点{0:n1，1:n4，3:n6}，其中0，1和3是重新映射的
	// /'a'，b'和'x'。
	table []*trieNode
}

func (t *trieNode) add(key, val string, priority int, r *genericReplacer) {
	if key == "" {
		if t.priority == 0 {
			t.value = val
			t.priority = priority
		}
		return
	}

	if t.prefix != "" {
		// 需要在多个节点之间拆分前缀。
		var n int // 最长公共前缀的长度
		for ; n < len(t.prefix) && n < len(key); n++ {
			if t.prefix[n] != key[n] {
				break
			}
		}
		if n == len(t.prefix) {
			t.next.add(key[n:], val, priority, r)
		} else if n == 0 {
			// 第一个字节不同，请在此处开始新的查找表。查找
			// 当前的t.prefix[0]将导致prefixNode，而
			// 查找键[0]将导致keyNode。
			var prefixNode *trieNode
			if len(t.prefix) == 1 {
				prefixNode = t.next
			} else {
				prefixNode = &trieNode{
					prefix: t.prefix[1:],
					next:   t.next,
				}
			}
			keyNode := new(trieNode)
			t.table = make([]*trieNode, r.tableSize)
			t.table[r.mapping[t.prefix[0]]] = prefixNode
			t.table[r.mapping[key[0]]] = keyNode
			t.prefix = ""
			t.next = nil
			keyNode.add(key[1:], val, priority, r)
		} else {
			// 在前缀的公共部分后插入新节点。
			next := &trieNode{
				prefix: t.prefix[n:],
				next:   t.next,
			}
			t.prefix = t.prefix[:n]
			t.next = next
			next.add(key[n:], val, priority, r)
		}
	} else if t.table != nil {
		// 插入到现有表中。
		m := r.mapping[key[0]]
		if t.table[m] == nil {
			t.table[m] = new(trieNode)
		}
		t.table[m].add(key[1:], val, priority, r)
	} else {
		t.prefix = key
		t.next = new(trieNode)
		t.next.add("", val, priority, r)
	}
}

func (r *genericReplacer) lookup(s string, ignoreRoot bool) (val string, keylen int, found bool) {
	// 将trie向下迭代到末尾，并获取具有最高优先级的值和keylen。
	bestPriority := 0
	node := &r.root
	n := 0
	for node != nil {
		if node.priority > bestPriority && !(ignoreRoot && node == &r.root) {
			bestPriority = node.priority
			val = node.value
			keylen = n
			found = true
		}

		if s == "" {
			break
		}
		if node.table != nil {
			index := r.mapping[s[0]]
			if int(index) == r.tableSize {
				break
			}
			node = node.table[index]
			s = s[1:]
			n++
		} else if node.prefix != "" && HasPrefix(s, node.prefix) {
			n += len(node.prefix)
			s = s[len(node.prefix):]
			node = node.next
		} else {
			break
		}
	}
	return
}

// GenericReplace是完全通用的算法。
// 当没有更快的东西可用时，它被用作后备。
type genericReplacer struct {
	root trieNode
	// tableSize是trie节点的查找表的大小。它是唯一密钥字节的
	// 数。
	tableSize int
	// 将trinode.table的关键字节映射到密集索引。
	mapping [256]byte
}

func makeGenericReplacer(oldnew []string) *genericReplacer {
	r := new(genericReplacer)
	// 找到使用的每个字节，然后为每个字节分配一个索引。
	for i := 0; i < len(oldnew); i += 2 {
		key := oldnew[i]
		for j := 0; j < len(key); j++ {
			r.mapping[key[j]] = 1
		}
	}

	for _, b := range r.mapping {
		r.tableSize += int(b)
	}

	var index byte
	for i, b := range r.mapping {
		if b == 0 {
			r.mapping[i] = byte(r.tableSize)
		} else {
			r.mapping[i] = index
			index++
		}
	}
	// 确保根节点使用查找表（用于性能）。
	r.root.table = make([]*trieNode, r.tableSize)

	for i := 0; i < len(oldnew); i += 2 {
		r.root.add(oldnew[i], oldnew[i+1], len(oldnew)-i, r)
	}
	return r
}

type appendSliceWriter []byte

// 写入缓冲区以满足io.Writer的要求。
func (w *appendSliceWriter) Write(p []byte) (int, error) {
	*w = append(*w, p...)
	return len(p), nil
}

// WriteString写入缓冲区而不使用字符串->[]字节->字符串分配。
func (w *appendSliceWriter) WriteString(s string) (int, error) {
	*w = append(*w, s...)
	return len(s), nil
}

type stringWriter struct {
	w io.Writer
}

func (w stringWriter) WriteString(s string) (int, error) {
	return w.w.Write([]byte(s))
}

func getStringWriter(w io.Writer) io.StringWriter {
	sw, ok := w.(io.StringWriter)
	if !ok {
		sw = stringWriter{w}
	}
	return sw
}

func (r *genericReplacer) Replace(s string) string {
	buf := make(appendSliceWriter, 0, len(s))
	r.WriteString(&buf, s)
	return string(buf)
}

func (r *genericReplacer) WriteString(w io.Writer, s string) (n int, err error) {
	sw := getStringWriter(w)
	var last, wn int
	var prevMatchEmpty bool
	for i := 0; i <= len(s); {
		// 快速路径：s[i]不是任何模式的前缀。
		if i != len(s) && r.root.priority == 0 {
			index := int(r.mapping[s[i]])
			if index == r.tableSize || r.root.table[index] == nil {
				i++
				continue
			}
		}

		// 如果上一个循环找到了空匹配项，则忽略该空匹配项。
		val, keylen, match := r.lookup(s[i:], prevMatchEmpty)
		prevMatchEmpty = match && keylen == 0
		if match {
			wn, err = sw.WriteString(s[last:i])
			n += wn
			if err != nil {
				return
			}
			wn, err = sw.WriteString(val)
			n += wn
			if err != nil {
				return
			}
			i += keylen
			last = i
			continue
		}
		i++
	}
	if last != len(s) {
		wn, err = sw.WriteString(s[last:])
		n += wn
	}
	return
}

// singleStringReplacer是在只有一个字符串要替换时使用的实现（该字符串包含多个字节）。
type singleStringReplacer struct {
	finder *stringFinder
	// value是找到该模式时替换该模式的新字符串。
	value string
}

func makeSingleStringReplacer(pattern string, value string) *singleStringReplacer {
	return &singleStringReplacer{finder: makeStringFinder(pattern), value: value}
}

func (r *singleStringReplacer) Replace(s string) string {
	var buf []byte
	i, matched := 0, false
	for {
		match := r.finder.next(s[i:])
		if match == -1 {
			break
		}
		matched = true
		buf = append(buf, s[i:i+match]...)
		buf = append(buf, r.value...)
		i += match + len(r.finder.pattern)
	}
	if !matched {
		return s
	}
	buf = append(buf, s[i:]...)
	return string(buf)
}

func (r *singleStringReplacer) WriteString(w io.Writer, s string) (n int, err error) {
	sw := getStringWriter(w)
	var i, wn int
	for {
		match := r.finder.next(s[i:])
		if match == -1 {
			break
		}
		wn, err = sw.WriteString(s[i : i+match])
		n += wn
		if err != nil {
			return
		}
		wn, err = sw.WriteString(r.value)
		n += wn
		if err != nil {
			return
		}
		i += match + len(r.finder.pattern)
	}
	wn, err = sw.WriteString(s[i:])
	n += wn
	return
}

// 字节置换器是在所有“旧”
// 和“新”值都是单个ASCII字节时使用的实现。
// 数组包含由旧字节索引的替换字节。
type byteReplacer [256]byte

func (r *byteReplacer) Replace(s string) string {
	var buf []byte // 延迟分配
	for i := 0; i < len(s); i++ {
		b := s[i]
		if r[b] != b {
			if buf == nil {
				buf = []byte(s)
			}
			buf[i] = r[b]
		}
	}
	if buf == nil {
		return s
	}
	return string(buf)
}

func (r *byteReplacer) WriteString(w io.Writer, s string) (n int, err error) {
	// TODO（bradfitz）：对s片使用io.WriteString，避免分配。
	bufsize := 32 << 10
	if len(s) < bufsize {
		bufsize = len(s)
	}
	buf := make([]byte, bufsize)

	for len(s) > 0 {
		ncopy := copy(buf, s)
		s = s[ncopy:]
		for i, b := range buf[:ncopy] {
			buf[i] = r[b]
		}
		wn, err := w.Write(buf[:ncopy])
		n += wn
		if err != nil {
			return n, err
		}
	}
	return n, nil
}

// byteStringReplacer是在所有
// “旧”值为单个ASCII字节，但“新”值大小不同时使用的实现。
type byteStringReplacer struct {
	// 替换包含由旧字节索引的替换字节片。
	// 一个nil[]字节意味着旧的字节不应该被替换。
	replacements [256][]byte
	// toReplace保留要替换的字节列表。根据toReplace 
	// 的长度和目标字符串的长度，使用Count或普通循环可能会更快。
	// 我们将单个字节存储为字符串，因为Count接受字符串。
	toReplace []string
}

// countCutOff控制字符串长度与替换数的比率
// which（*byteStringReplacer）.Replace开关算法。
// 对于替换长度比大于该值的字符串，
// 我们调用Count，用于从替换开始的每次替换。
// 对于字符串，由于计数开销，我们使用简单循环的比率较低。
// countCutOff是一个经验确定的开销乘数。
// TODO（tocarip）一旦我们有了基于寄存器的abi/中间堆栈内联，就可以重新访问。
const countCutOff = 8

func (r *byteStringReplacer) Replace(s string) string {
	newSize := len(s)
	anyChanges := false
	// 使用计数是否更快？
	if len(r.toReplace)*countCutOff <= len(s) {
		for _, x := range r.toReplace {
			if c := Count(s, x); c != 0 {
				// 1是因为我们用len（replacements[b]）字节替换1字节。
				newSize += c * (len(r.replacements[x[0]]) - 1)
				anyChanges = true
			}

		}
	} else {
		for i := 0; i < len(s); i++ {
			b := s[i]
			if r.replacements[b] != nil {
				// 参见上文中对-1 
				newSize += len(r.replacements[b]) - 1
				anyChanges = true
			}
		}
	}
	if !anyChanges {
		return s
	}
	buf := make([]byte, newSize)
	j := 0
	for i := 0; i < len(s); i++ {
		b := s[i]
		if r.replacements[b] != nil {
			j += copy(buf[j:], r.replacements[b])
		} else {
			buf[j] = b
			j++
		}
	}
	return string(buf)
}

func (r *byteStringReplacer) WriteString(w io.Writer, s string) (n int, err error) {
	sw := getStringWriter(w)
	last := 0
	for i := 0; i < len(s); i++ {
		b := s[i]
		if r.replacements[b] == nil {
			continue
		}
		if last != i {
			nw, err := sw.WriteString(s[last:i])
			n += nw
			if err != nil {
				return n, err
			}
		}
		last = i + 1
		nw, err := w.Write(r.replacements[b])
		n += nw
		if err != nil {
			return n, err
		}
	}
	if last != len(s) {
		var nw int
		nw, err = sw.WriteString(s[last:])
		n += nw
	}
	return
}
